Preliminary Readings

Ders Kitabı

• An Introduction to Statistical Learning with Applications in R, Gareth James, Daniela Witten, Trevor Hastie and Robert Tibshirani, Bölüm 9

Bazı Slaytlar Ek Bir Kitap Bölümünden Uyarlanmıştır

Hands-On Machine Learning with R

Bazı Slaytlar Bu Eğitim Modülünden Uyarlanmıştır

Freie Universität Berlin Learning Module

Sınıflandırma

• Karar Ağacı (Sınıflandırma Ağacı), Decision Tree

• K-En Yakın Komşu (KNN), K-Nearest Neighbors

• Doğrusal Olasılık Modeli, Linear Probability Model

• Lojistik Regresyon & Probit Regresyon Logit and Probit Regressions

• Destek Vektör Makinesi, Support Vector Machines, SVM

• Boosting ve Bagging, Makine Öğrenmesi Dersi

• Ayırıcı Analiz (Ders içerisinde tartışılmayacak), Discriminant Analysis

Öğrenme Hedefleri

• Denetimli Öğrenme kapsamında (girdi(ler)-çıktı ilişkisi)
  
• Sınıflandırma Görevleri İçin
  • Başlangıçta İkili Sınıflandırma amacıyla geliştirilmiştir
    
  • Çok Sınıflı Sınıflandırma da mümkündür
• Kutudan çıktığı gibi çok iyi sonuçlar veren sınıflayıcılardan biridir

Anahtar Kavramlar:

• Maksimum marj sınıflayıcı (Maximal margin classifier): basit ve sezgisel bir sınıflayıcı

• Destek vektör sınıflayıcı (Support vector classifier): maksimum marj sınıflayıcının bir genişletmesidir

• Destek vektör makinesi (Support vector machine, SVM): destek vektör sınıflayıcının daha da geliştirilmiş halidir

SVM: Yorumlanabilirlik / Esneklik

SVM

• Basit bir örnek: Tartışma

SVM

• \(x\) sembolünü inceleyin

Veya

Hiper Düzlem (Hyperplane)

• Hiper düzlem: \(p\) boyutlu bir uzayda hiper düzlem, boyutu \(p - 1\) olan düz bir alt uzay olarak tanımlanır (yani doğrusal bir denklemle ifade edilir)

\(f\left(X\right) = \beta_0 + \beta_1 X_1 + \dots + \beta_p X_p = 0\)

Örneğin, \(p=2\) iki boyutlu bir uzayı, \(p=3\) ise üç boyutlu bir uzayı temsil eder (Hands-On Machine Learning with R kitabından uyarlanmıştır)

• Ve hiper düzlemlerin denklemleri

\(p=2 \implies \beta_0 + \beta_1 X_1 + \beta_2 X_2 = 0\) (a line) and,

\(p=3 \implies \beta_0 + \beta_1 X_1 + \beta_2 X_2 + \beta_3 X_3 = 0\) (a plane)

Hiper Düzlem

• Diyelim ki \(X = (X_1, X_2, \dots, X_p)^T\) vektörü, $ _0 + _1 X_1 + + _p X_p = 0$ denklemine uymuyor. Eğer bu nokta hiper düzlemin bir tarafında yer alıyorsa:

\(f\left(X\right) = \beta_0 + \beta_1 X_1 + \dots + \beta_p X_p > 0\)

veya diğer tarafında yer alıyorsa

\(f\left(X\right) = \beta_0 + \beta_1 X_1 + \dots + \beta_p X_p < 0\)

• Yani, bir hiper düzlem \(p\) boyutlu uzayı iki yarıya bölüyor gibi düşünülebilir

• \(f(X)\) fonksiyonu ayrıcı bir hiper düzlemdir

• İki sınıfı temsil eden \(y_i = {1, -1}\) ifadesini kullanalım; burada \(f(X) > 0\) için \(y_i = 1\) ve \(f(X) < 0\) için \(y_i = -1\) olur

Başka Bir Sentetik Örnek

• Örnek, Hands-On Machine Learning with R kitabından uyarlanmıştır

• Sınırsız sayıda ayıran hiperdüzlem çizilebilir

• Optimal olan hangisidir?

Başka bir Sentetik Örnek

• Farklı yaklaşımlar kullanılarak elde edilen hiperdüzlemler (GLM: Lojistik, LDA: Doğrusal Ayırt Etme Analizi, HMC: Optimal Ayıran Hiperdüzlem)

Optimal Ayıran Hiperdüzlem

• Maksimal marj hiperdüzlemi ve Optimal Ayıran Hiperdüzlem genel olarak birbirinin yerine eşanlamlı olarak kullanılır

• OSH (Optimal Ayıran Hiperdüzlem) optimaldir. İki sınıfı, sınıfların her birinden en yakın noktalara olan mesafeyi maksimize ederek ayırır

• Bu maksimize edilmiş (veya en üst düzeye çıkarılmış) mesafe marj \(M\) olarak adlandırılır (Maksimal Marj Sınıflandırıcısı)

Geometrik olarak:

• Her bir sınıfı çevreleyen çokgenleri çizin (konveks zarf)

• İki çokgeni birleştiren en kısa doğru parçasını çizin (iki sınıf arasındaki kesikli çizgi)

• Bu doğru parçasının orta dikmesi Optimal Ayıran Hiperdüzlemdir

• Marj sınırları, ayıran hiperdüzleme paralel olarak destek vektörlerinden (support vectors) (kırmızı üçgen olarak gösterilen 2 nokta) geçer

• Bu örnekte iki sınıf doğrusal bir hiperdüzlem kullanılarak ayrılabilir

• Kısaca, maksimal marj hiperdüzlemi optimizasyon probleminin çözümüdür

\(\begin{align} &\underset{\beta_0, \beta_1, \dots, \beta_p}{\text{maximize}} \quad M \\ &\text{subject to} \quad \begin{cases} \sum_{j = 1}^p \beta_j^2 = 1,\\ y_i\left(\beta_0 + \beta_1 x_{i1} + \dots + \beta_p x_{ip}\right) \ge M,\quad i = 1, 2, \dots, n \end{cases} \end{align}\)

Esnek Marj Sınıflandırıcısı

• Bazen mükemmel ayırma başarılabilir, ancak istenmez

• (0.5, 1) noktasına tek bir aykırı değer ekleyelim

• Veri hala doğrusal bir çizgi ile mükemmel şekilde ayrılabilir

• Lojistik regresyon ve HMC kullanılarak elde edilen karar sınırları yeni verilere iyi genelleme yapmaz (öznitelik uzayındaki aykırı değerlere -outliers- karşı dayanıklı değildirler)

• LDA modeli daha makul bir karar sınırı üretiyor gibi görünmektedir

• Kısıtlamalar, esnek marj sınıflandırıcısı (soft margin classifier) olarak adlandırılan daha iyi bir karar sınırı elde etmek için gevşetilebilir

Esnek Marj Sınıflandırıcısı

Maksimizasyon problemi, bireysel gözlemlerin marjın veya hiperdüzlemin yanlış tarafında olmasına izin veren basit bir ekleme olan \(\epsilon_i\) (gevşeklik değişkeni, slack variable) ve pozitif ayarlanabilir bir hiperparametre olan \(C\) (**_bütçe**) ile katı (hard) marja benzerdir:

\[\begin{align} &\underset{\beta_0, \beta_1, \dots, \beta_p}{\text{maximize}} \quad M \\ &\text{subject to} \quad \begin{cases} \sum_{j = 1}^p \beta_j^2 = 1,\\ y_i\left(\beta_0 + \beta_1 x_{i1} + \dots + \beta_p x_{ip}\right) \ge M\left(1 - \epsilon_i\right), \quad i = 1, 2, \dots, n\\ \epsilon_i \ge 0, \\ \sum_{i = 1}^n \epsilon_i \le C\end{cases} \end{align}\]

• \(\epsilon_i\) bize \(i\). gözlemin nerede bulunduğunu söyler:

  • Eğer \(\epsilon_i=0\) ise, \(i\). gözlem marjın doğru tarafındadır
    
  • Eğer \(\epsilon_i > 0\) ise, \(i\). gözlem marjın yanlış tarafındadır, bu gözlem marjı ihlal etmiştir
    
  • Eğer \(\epsilon_i > 1\) ise, \(i\). gözlem hiperdüzlemin yanlış tarafındadır

• Doğrudan marjın üzerinde veya kendi sınıfları için marjın yanlış tarafında bulunan gözlemler destek vektörleri, support vectors olarak bilinir. Bu gözlemler destek vektör sınıflandırıcısını etkiler

• \(C\), \(\epsilon_i\)’lerin toplamını sınırlar ve böylece marj ihlallerinin sayısını ve şiddetini belirler

• \(C\) küçük olduğunda (ihlal maliyeti yüksek olduğunda) optimizasyon, nadiren ihlal edilen dar marjlar bulmaya çalışır, yani verilere yüksek düzeyde uyum sağlar ki bu düşük yanlılığa (bias) ancak yüksek varyansa sahip olabilir

• \(C\) yüksek olduğunda daha fazla ihlal vardır, yani verilere daha az katı uyum sağlanır ki bu yüksek yanlılığa fakat daha düşük varyansa sahip olabilir

Marjın ve Hiperdüzlemin Yanlış Tarafı

• Sol: 1 ve 8 numaralı noktalar marjın yanlış tarafındadır, hiçbir gözlem hiperdüzlemin yanlış tarafında değildir

• Sağ: 12 ve 11 numaralı noktalar hiperdüzlemin yanlış tarafındadır, 1 ve 8 numaralı noktalar marjın yanlış tarafındadır

Sentetik Veri

Başka Bir Sentetik Veri Örneği

Esnek Marj (Soft Margin)

• İhlal maliyetini (the cost of violation) seçmek önemlidir. Yetersiz öğrenmeden (underfitting) kaçınırken, aynı zamanda aşırı öğrenmeden (overfitting) de kaçınırız. Denge önemlidir. Çapraz doğrulama iyi olanı seçmemize yardımcı olur

• Esnek marj sınıflandırıcısı (Soft margin classifier) aykırı değerlere ve gürültülü verilere karşı dayanıklılık (robustness) sağlar

• Esnek marj sınıflandırıcısının performansı, maliyet değerinin seçimine duyarlıdır

• Maliyet parametresinin eklenmesi esnekliği artırır

• Choosing **** is important. While we avoid underfitting, we also avoid overfitting. The balance is important. Cross-validation helps us to choose the good one

• provides robustness against outliers and noisy data

• The performance of soft margin classifier is sensitive to the choice of the value of the cost

• Introducing the cost parameter increases flexibility

Destek Vektör Makineleri

• Şimdiye kadar sadece doğrusal karar sınırları tartışıldı (pratikte kullanışlı olmak için çok kısıtlayıcı)

• Eğer ilişki doğrusal değilse, doğrusal karar sınırı yetersiz kalır

• Kernel hilesi bunun üstesinden gelmek için cevap olabilir

• Kernel hilesi, temel fonksiyonları kullanarak (kestiricilerin karesel, kübik terimler vb. içeren polinom fonksiyonları gibi fonksiyonlarını kullanarak) öznitelik uzayını genişletmek için kullanılabilir

• Bu büyütülmüş (kernel kaynaklı) öznitelik uzayında, bir hiperdüzlem genellikle iki sınıfı ayırabilir

  • Karar sınırı genişletilmiş öznitelik uzayında doğrusaldır
    
  • Karar sınırı orijinal öznitelik uzayına geri dönüştürüldüğünde doğrusal değildir

Örnek

• Sol: ikili sınıflandırma problemi (doğrusal olmayan durum)

• Sağ: Üçüncü bir öznitelik, \(X_3 = X_1^2 + X_2^2\) eklenerek genişletilmiş öznitelik uzayı (derecesi 2 olan polinom çekirdek fonksiyonu)

• \(X3\) tüm yeşil noktalar için daha küçüktür, bu nedenle bu bir hiperdüzlem ile mükemmel şekilde ayrılabilir

• Sonuçtaki karar sınırı

• Fikir, bir hiperdüzlemle ayrılabilir bir öznitelik uzayı elde etmek için öznitelik uzayını büyüterek üzere kernel hilesini kullanmaktır

• Destek vektör makinesi (SVM) öznitelik uzayını belirli bir şekilde, kernels (çekirdekler) kullanarak büyütmenin sonucu olan destek vektör sınıflandırıcısının bir uzantısıdır

Kernel Fonksiyonları

Yaygın kullanılan Kernel Fonksiyonarı

• \(d}\) derece polinom: \(K\left(x, x'\right) = \gamma\left(1 + \langle x, x' \rangle\right)^d\) where inner product, \(\langle x, x' \rangle = \sum_{i = 1}^n x_i x_i'\)

• Radial basis fonksiyonu: \(K\left(x, x'\right) = \exp\left(\gamma \lVert x - x'\rVert ^ 2\right)\)

• Hyperbolik tanjant (Sigmoid Kernel): \(K\left(x, x'\right) = \tanh\left(k_1 x \cdot x' + k_2\right)\)

Örnek

Daha Fazla Örnek

• Polinom Kernel Örneği

• Radial Basis Function (RBF) veya Gaussian Kernel

• Sigmoid Kernel

İkiden Fazla Sınıflı SVM’ler

• Bire-Karşı-Bir Sınıflandırma (One-Versus-One Classification)

  • Bire-karşı-bir veya başka deyişle tüm-çiftler yaklaşımı \(\frac{K!}{2!(K-2)!}\) tane SVM oluşturur, her biri bir çift sınıfı karşılaştırır

  • Nihai sınıflandırma, test gözlemini bu ikili sınıflandırmalarda en sık atandığı sınıfa atayarak gerçekleştirilir

• Bire-Karşı-Hepsi Sınıflandırma (One-Versus-All Classification)

  • \(K\) tane SVM oluşturulur, her biri \(i\). sınıfı geri kalan sınıflarla karşılaştırır

  • Nihai sınıflandırma, test gözlemini en yüksek marja sahip SVM’ye göre sınıfa atayarak gerçekleştirilir